先簡單回顧一下，今天預計分析兩個題目：

• 26. Remove Duplicates from Sorted Array
• 167. Two Sum II - Input array is sorted

26. Remove Duplicates from Sorted Array

• 題目連結：https://leetcode.com/problems/valid-parentheses/

• 題目敘述：

  • 題目會給你一個從小排序到大的資料，但是裡面有重複的元素，你需要把他刪掉
  • 有些語言是不能把資料裡的元素刪掉 ( array 長度不能被改變)，所以你需要把後面所有元素往前平移
  • 不過我們這邊使用的是 python，可以刪除任意位置的元素 ，所以只要遇到多餘的就刪掉即可

  

• 測資的 Input/Output

  • 題目如果給你 [1,1,2] 那你要把多餘的元素刪掉，並回傳不重複元素個數

    

• python 實作如下：

  • 根據題目要求，不能使用額外的空間，那麼就使用 Two-pointer 的概念，
    • nums 把不重複的資料往前填
      1. 初始狀態，我們將 k 跟 j 從第2個數字開始看，因為第一個數字一定不重複，所以直接從第二個看
         1. j 會從第2個數字開始走訪每一個位置，一次一格，直到指到尾
         2. k 會先停在第2個數字，當 j 找到不一樣的元素，那 nums[k] 會儲存 nums[j]，然後 k 再往後一格，等待 j 再次找到不同的元素
      2. 隨著 j 的走訪，每次會比較第 j 個跟第 j-1 個數字是否一致
         1. 若不一致，代表第 j 個值不是重複元素，就可以安心把 第 k 個儲存 第 j 個的值，並且 k 再往右移動一格 ( 在尚未遇到重複元素時，j 跟 k 都會指向同一個地方)
         2. 若一致，代表第 j 個是重複元素，那就不做任何事，直到 j 指向非重複元素，那麼第 k 個位置( k 停在遇到的第一個重複元素的位置)，就會儲存第 j 個的值( j 停在非重複元素的位置)

  

- python 實作

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
#       k 會用來計算不重複元素的位置
        k = 1
#       j 會走得比較快，把不重複的值，丟給 k 位置儲存
        for j in range(1, len(nums)):
#           判斷第 j 個位置跟第 j-1 的位置，是否不相等，若不相等，就把 nums[k] 儲存 nums[j]，並 k 向右移動
            if nums[j] != nums[j - 1]:
                nums[k] = nums[j]
                k += 1

        return k

• 非 Two-pointer 解法
  • python nums 把資料 pop 出來
    • 每次遇到重複的值，就將他刪掉，不過刪掉後，後面的資料會直接遞補刪掉的位置，所以要進行 j -=1，免得比對的時候跳過新遞補的數字

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 1
        while j < len(nums):
            if nums[j] == nums[j-1]:
                nums.pop(j)  
                j -= 1
            j += 1
        return len(nums)

• python 使用內建的 function
  • set 會自動把多餘的元素刪除
  • 接著再用 sort 重新排列
  • nums[:] 則是可以把 nums 全部的資料改成儲存剛剛刪除並排列好的

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        nums[:] = sorted(set(nums))
        return len(nums)

167. Two Sum II - Input array is sorted

• 題目連結：https://leetcode.com/problems/valid-parentheses/

• 題目敘述：

  • 題目會給你一個從小排序到大的資料，跟希望找到的兩數相加的和 (target)

  • 你需要找出哪兩個位置的值，相加會等於 target

  • 哪兩個位置的值相加為 target，只會有一種答案

  • 同一個元素不能加兩次

    

• 測資的 Input/Output

  • 題目會給你一個遞增的數列，跟希望找到的目標總和 (target)

  • 回傳一個 list 結構的資料，裡面要包含相加會等於 target 的 index

    

• python 實作

  

  

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers)-1

        while not numbers[left] + numbers[right] == target:
            while numbers[left] + numbers[right] > target and left != right:
                right -= 1 
            while numbers[left] + numbers[right] < target and left != right:
                left += 1

        return [left+1,right+1]